import java.util.ArrayList;
import java.util.List;

public class SlidingWindow {
    public List<Integer> findAnagrams(String s, String p) {
        int pLen = p.length();
        int sLen = s.length();
        int[] arrP = new int[128];
        for (int i = 0; i < pLen; i++) {
            char ch = p.charAt(i);
            arrP[ch]++;
        }
        List<Integer> ret = new ArrayList<>();
        int[] arrSub = new int[128];
        for (int left = 0, right = 0, count = 0; right < sLen; right++) {
            char in = s.charAt(right);
            arrSub[in]++;
            if (arrSub[in] <= arrP[in]) {//字符有效
                count++;
            }
            if (right - left >= pLen) {
                char out = s.charAt(left++);
                if (arrSub[out] <= arrP[out]) {
                    count--;
                }
                arrSub[out]--;
            }
            if (count == pLen) {
                ret.add(left);
            }
        }
        return ret;
    }

    public List<Integer> findAnagrams1(String s, String p) {
        int pLen = p.length();
        int sLen = s.length();
        int[] arrP = new int[128];
        for (int i = 0; i < pLen; i++) {
            char ch = p.charAt(i);
            arrP[ch]++;
        }
        List<Integer> ret = new ArrayList<>();
        int[] arrSub = new int[128];
        for (int left = 0, right = 0; right < sLen; right++) {
            char in = s.charAt(right);
            // if (arrSub[in] == 0) {
            //     kinds++;
            // }
            arrSub[in]++;
            if (right - left >= pLen) {
                char out = s.charAt(left++);
                arrSub[out]--;
            }
            if (isSameArray(arrP, arrSub)) {
                ret.add(left);
            }
        }
        return ret;
    }

    private boolean isSameArray(int[] arr1, int[] arr2) {//比较两个数组是否相同
        int n1 = arr1.length;
        int n2 = arr2.length;
        for (int i = 0; i < n1; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }
}
